home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / planar_map.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  5.5 KB  |  219 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  planar_map.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #ifndef LEDA_PLANAR_MAP_H
  18. #define LEDA_PLANAR_MAP_H
  19.  
  20. #include <LEDA/graph.h>
  21.  
  22. class i_face;
  23.  
  24. typedef i_face* face;
  25.  
  26. class i_face {
  27.  
  28. friend class planar_map;
  29.  
  30.  edge      head;     // first edge of face
  31.  list_item loc;      // location in F_list
  32.  GenPtr    inf;      // user defined information
  33.  
  34.  planar_map*  g;     // face of (*g)
  35.  
  36.  
  37.  i_face(GenPtr x, planar_map* G) 
  38.  { 
  39.    inf = x ; 
  40.    head = nil; 
  41.    loc = nil; 
  42.    g = G;
  43.   }
  44.  
  45.  
  46.   LEDA_MEMORY(i_face)
  47.  
  48. FRIEND_INLINE planar_map* graph_of(face);
  49.  
  50. };
  51.  
  52. inline planar_map* graph_of(face f) { return f->g; }
  53.  
  54.  
  55.  
  56.  
  57.  
  58. extern int STRAIGHT_LINE_EMBEDDING(graph& G, node_array<int>& xcoord,
  59.                                             node_array<int>& ycoord);
  60.  
  61. class planar_map : public graph {
  62.  
  63. list<face>       F_list;
  64.  
  65. face  new_face(GenPtr i=0);
  66. void  del_face(face f) { F_list.del(f->loc); delete f; }
  67.  
  68. face& FACE(edge e) { return (face&)(e->data[0]);  }
  69.  
  70. virtual void copy_face_entry(GenPtr&)  const {}
  71. virtual void init_face_entry(GenPtr&)        {}
  72. virtual void clear_face_entry(GenPtr&) const {}
  73.  
  74. /* inherited from graph:
  75. virtual void copy_node_entry(GenPtr&)  const {}
  76. virtual void init_node_entry(GenPtr&)        {}
  77. virtual void clear_node_entry(GenPtr&) const {}
  78. */
  79.  
  80. virtual void print_face_entry(GenPtr&) const {}
  81.  
  82. public:
  83.  
  84.  
  85. planar_map(const graph&);
  86.  
  87. planar_map() {}
  88.  
  89. virtual ~planar_map() { clear(); }
  90.  
  91. void       clear();
  92.  
  93. void       init_entries();
  94.  
  95.  
  96. list<node> adj_nodes(face)   const;
  97. list<node> adj_nodes(node v) const { return graph::adj_nodes(v); }
  98.  
  99. list<edge> adj_edges(face)   const;
  100. list<edge> adj_edges(node v) const { return graph::adj_edges(v); }
  101.  
  102. const list<face>& all_faces()       const { return F_list; }
  103.  
  104. list<face> adj_faces(node)   const;
  105.  
  106. face       adj_face(edge e)  const { return face(e->data[0]); }
  107.  
  108. list<edge> triangulate();
  109.  
  110. edge reverse(edge e)         const { return edge(e->rev); }
  111.  
  112. edge first_face_edge(face f) const { return f->head; }
  113. edge succ_face_edge(edge e)  const { return cyclic_adj_succ(reverse(e)); } 
  114. edge pred_face_edge(edge e)  const { return reverse(cyclic_adj_pred(e)); } 
  115.  
  116. edge next_face_edge(edge e)  const  
  117. { e = succ_face_edge(e);
  118.   return (e==adj_face(e)->head) ? nil : e;
  119. }
  120.  
  121. face first_face() const { return F_list.head(); }
  122.  
  123. face next_face(face f) const
  124. { list_item it = F_list.succ(f->loc);
  125.   return (it) ? F_list.contents(it) : nil;
  126. }
  127.  
  128.  
  129. edge    new_edge(edge,edge,GenPtr=0);
  130. void    del_edge(edge,GenPtr=0);
  131.  
  132. edge    split_edge(edge,GenPtr=0);
  133.  
  134. node    new_node(const list<edge>&, GenPtr=0);
  135. node    new_node(face, GenPtr=0);
  136.  
  137. GenPtr& entry(face f)         { return f->inf; }
  138. GenPtr& entry(node v)         { return graph::entry(v); }
  139.  
  140. GenPtr  inf(face f)     const { return f->inf; }
  141. GenPtr  inf(node v)     const { return graph::inf(v); }
  142.  
  143. int     straight_line_embedding(node_array<int>& x, node_array<int>& y)
  144.                               { return STRAIGHT_LINE_EMBEDDING(*this,x,y); }
  145.  
  146.  
  147. };
  148.  
  149.  
  150. //------------------------------------------------------------------------------
  151. // PLANAR_MAP: generic planar map
  152. //------------------------------------------------------------------------------
  153.  
  154.  
  155. template <class vtype, class ftype>
  156.  
  157. class _CLASSTYPE PLANAR_MAP : public planar_map {
  158.  
  159. vtype X;
  160. ftype Y;
  161.  
  162. void init_node_entry(GenPtr& x)  { Init(X); x=Copy(X); }
  163. void init_face_entry(GenPtr& x)  { Init(Y); x=Copy(Y); }
  164.  
  165. void copy_node_entry(GenPtr& x)  const { x=Copy(ACCESS(vtype,x)); }
  166. void copy_face_entry(GenPtr& x)  const { x=Copy(ACCESS(ftype,x)); }
  167.  
  168. void clear_node_entry(GenPtr& x) const { Clear(ACCESS(vtype,x)); }
  169. void clear_face_entry(GenPtr& x) const { Clear(ACCESS(ftype,x)); }
  170.  
  171. void print_node_entry(ostream& o, GenPtr& x)  const
  172. { o << "("; Print(ACCESS(vtype,x),o); o << ")"; }
  173.  
  174. void print_edge_entry(ostream& o, GenPtr& x)  const
  175. { o << "(" << int(x) << ")"; }
  176.  
  177. public:
  178.  
  179.    vtype  inf(node v)    const   { return ACCESS(vtype,planar_map::inf(v)); }
  180.    ftype  inf(face f)    const   { return ACCESS(ftype,planar_map::inf(f)); }
  181.    vtype& entry(node v)          { return ACCESS(vtype,planar_map::entry(v)); }
  182.    ftype& entry(face f)          { return ACCESS(ftype,planar_map::entry(f)); }
  183.    vtype& operator[] (node v)    { return entry(v); }
  184.    ftype& operator[] (face f)    { return entry(f); }
  185.    void   assign(node v,vtype a) { planar_map::entry(v) = Copy(a); }
  186.    void   assign(face f,ftype a) { planar_map::entry(f) = Copy(a); }
  187.  
  188.    edge   new_edge(edge e1, edge e2)
  189.                           { return planar_map::new_edge(e1,e2,0); }
  190.    edge   new_edge(edge e1, edge e2, ftype a)
  191.                           { return planar_map::new_edge(e1,e2,Convert(a)); }
  192.  
  193.    edge   split_edge(edge e, vtype a)
  194.                           { return planar_map::split_edge(e,Convert(a)); }
  195.  
  196.    node   new_node(list<edge> el,vtype a)
  197.                           { return planar_map::new_node(el,Convert(a)); }
  198.  
  199.    node   new_node(face f,vtype a)
  200.                           { return planar_map::new_node(f,Convert(a)); }
  201.  
  202.    void print_node(node v) const { cout << "["; Print(inf(v)); cout << "]";}
  203.  
  204.    PLANAR_MAP(const GRAPH<vtype,ftype>& G) : planar_map((graph&)G)   {}
  205.    PLANAR_MAP() {}
  206.   ~PLANAR_MAP() { clear(); }
  207.  
  208. };
  209.  
  210.  
  211. #define forall_face_edges(e,F)\
  212. for(e=graph_of(F)->first_face_edge(F); e; e=graph_of(F)->next_face_edge(e)) 
  213.  
  214. #define forall_faces(f,G)\
  215. for(f=G.first_face(); f; f=G.next_face(f)) 
  216.  
  217.  
  218. #endif
  219.